package leetcode;
/**
 * 160.相交链表
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 * 注意，函数返回结果后，链表必须 保持其原始结构 。
 */
public class Num_160 {
    //方法一：殊途同归，先判断是否相交；再让两个动点离交点的距离相同时遍历
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode nodeA = headA, nodeB = headB;
        //两个计步器，分别记录A和B走到尾节点的步数
        int countA = 0, countB = 0;
        while(nodeA.next != null){
            nodeA = nodeA.next;
            countA ++;
        }
        while(nodeB.next != null){
            nodeB = nodeB.next;
            countB ++;
        }
        //如果最后A和B不在同一个位置，说明两个链表没有相交
        if(nodeA != nodeB){
            return null;
        }
        /**
         * 如果有交点，则相交之后的节点数一定相同；相交之前的节点数可能不同
         * A和B的节点数相差 |countA-countB|
         * 再次从头开始遍历A和B，让节点多的那个先走，直到A和B离交点的距离相同时，
         * 再让它俩同时向后遍历，每走一步比较一下位置，当位置重叠时，就是交点处
         */
        nodeA = headA;
        nodeB = headB;
        int disparity = Math.abs(countA-countB);
        if(countA > countB){
            while(disparity > 0){
                nodeA = nodeA.next;
                disparity --;
            }
        }else{
            while(disparity > 0){
                nodeB = nodeB.next;
                disparity --;
            }
        }
        //此时，A和B离交点的距离相同
        while(nodeA != nodeB){
            nodeA = nodeA.next;
            nodeB = nodeB.next;
        }
        return nodeA;
    }

    /** 上面的简写 **/
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB){
        ListNode nodeA = headA, nodeB = headB;
        //1.相交时刚好返回交点
        //2.不相交两个同时走到null
        /**
         * 这么想，如果A和B的长度相同，就很容易理解下面的循环
         * 如果A!=B，
         * 一定是(走短路的)先走完,让它紧接着换长路走；
         * 当另一个也走完时，让它换到短路上；
         * 此时(先走完的那个)已经在长路上走了|A-B|的长度，而另一个在短路的起点；
         * 这时，两者距离(交点or终点null)的距离相同
         */
        //A + C + B = B + C + A
        while(nodeA != nodeB){
            //三目运算符
            nodeA = (nodeA == null) ? headB : nodeA.next;
            nodeB = (nodeB == null) ? headA : nodeB.next;
        }
        return nodeA;
    }
}
